package OfferLanQiaoBei.a_13届蓝桥真题;

import java.util.HashMap;
import java.util.Scanner;

/*
小蓝老师教的编程课有N名学生，编号依次是1...N.
第i号学生这学期剛题的数量是A.
对于每一名学生，请你计算他至少还要再刷多少道题，
才能使得全班刷题比他多的学生数不超过刷题比他少的学生数。
5
12 10 15 20 6

0 3 0 0 7


利用二分法找到中位数median的起止索引（中位数可能是很多个相同的数字），由此得出大于median的个数（big），和小于median的个数（small）。
对每一个数字进行判断（关键思路是对median进行分类判断）：

    如果该数字大于median（即在数组的后半段），则不用多做题。
    如果该数字就是median：
        如果 big <= small，也不需多做题就已满足题意。
        如果 big > small，则只需要多做一道题就可以打破平衡。
    如果该数字比median小（即在数组的前半段）：
        如果 small > big，该数字只需要成为中位数即可。
        如果 small <= big，该数字需要比中位数多一个数字才可打破平衡。
 */
public class d最少刷题数自己优化 {
	public static void main(String[] args) {
		d最少刷题数自己优化 test = new d最少刷题数自己优化();
		test.useDeal();
	}
	
	public void useDeal() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = scanner.nextInt();
		}
		dealSimple(arr, N);
	}
	
	public void dealSimple(int[] arr, int N) {
		int[] mid = new int[2];
		int[] helper = arr.clone();
		quickSortThree(helper, 0, N - 1);
		mid = partitionThree(helper, 0, N - 1);
//		System.out.println(mid[0] + " " + mid[1]);
		int median = helper[mid[1]];
		int big = N - 1 - mid[1];
		int small = mid[0];
		for (int i = 0; i < N; i++) {
//			if (i == N - 1) {
//				
//			}
			if (arr[i] > median) {
				System.out.print(0 + " ");
			} else if (arr[i] == median) {
				if (big <= small) {
					System.out.print(0 + " ");
				} else {
					System.out.print((median + 1 - arr[i]) + " ");
				}
			} else if (arr[i] < median) {
				if (big < small) {
					System.out.print((median - arr[i]) + " ");
				} else {
					System.out.print((median + 1 - arr[i]) + " ");
				}
			}
		}
	}
	
	public void deal(int[] arr, int N) {
		int[] mid = new int[2];
		int[] helper = arr.clone();
		quickSortThree(helper, 0, N - 1);
		for (int i = 0; i < N; i++) {
			if (arr[i] > helper[mid[1]]) {
				System.out.print(0 + " ");
			} else if (arr[i] == helper[mid[1]]) {
				if (N - 1 - mid[1] <= mid[0]) {
					System.out.println(0 + " ");
				} else {
					System.out.println((helper[mid[1]] + 1 - arr[i]) + " ");
				}
			} else if (arr[i] < helper[mid[1]]) {
				if (N - 1 - mid[1] < mid[0]) {
					System.out.println((helper[mid[1]] - arr[i]) + " ");
				} else {
					System.out.println((helper[mid[1]] + 1 - arr[i]) + " ");
				}
			}
		}
	}
	
	public void quickSortThree(int[] arr, int p, int r) {
		if (p < r) {
			if (r - p + 1 <= 8) {
				insertSort(arr, p, r);
			} else {
				int[] q = partitionThree(arr, p, r);
				quickSortThree(arr, p, q[0] - 1);
				quickSortThree(arr, q[1] + 1, r);
			}
		}
		
	}
	
	public int[] partitionThree(int[] arr, int p, int r) {
		int e = p + 1;
		int sp = p + 1;
		int bigger = r;
		int midIndex = getMedian(arr, p, r);
		swap(arr, p, midIndex);
		int piovet = arr[p];
		int[] equalNumber = new int[2];
		while (sp <= bigger) {
			while (sp <= bigger && arr[sp] <= piovet) {
				if (arr[sp] < piovet && sp == e) {
					sp++;
					e++;
				} else if (arr[sp] < piovet && sp != e) {
					swap(arr, e, sp);
					sp++;
					e++;
				} else {
					sp++;
				}
			}
			while (sp <= bigger && arr[bigger] > piovet) {
				bigger--;
			}
			if (sp < bigger) {
				swap(arr, sp, bigger);
			}
		}
		swap(arr, p, e - 1);
		equalNumber[0] = e - 1;
		equalNumber[1] = bigger;
		return equalNumber;
	}
	
	public int getMedian(int[] arr, int p, int r) {
		int size = r - p + 1;
		int groupSize = (size % 5 == 0) ? (size / 5) : ((size / 5) + 1);
		int indexOfMedians = 0;
		int[] medians = new int[groupSize];
		HashMap<Integer, Integer> medainsValueIndex = new HashMap<Integer, Integer>();
		for (int i = 0; i < groupSize; i++) {
			if (i == groupSize - 1) {
				insertSort(arr, p + i * 5, r);
				medians[indexOfMedians++] = arr[(p + i * 5 + r) >>> 1];
				medainsValueIndex.put(arr[(p + i * 5 + r) >>> 1], (p + i * 5 + r) >>> 1);
			} else {
				insertSort(arr, p + i * 5, p + i * 5 + 4);
				medians[indexOfMedians++] = arr[p + i * 5 + 2];
				medainsValueIndex.put(arr[p + i * 5 + 2], p + i * 5 + 2);
			}
		}
		insertSort(medians, 0, groupSize - 1);
		return medainsValueIndex.get(medians[(groupSize - 1) >>> 1]);
	}
	
	public void insertSort(int[] arr, int p, int r) {
		int brfore_i = 0;
		int value_i = 0;
		for (int i = p + 1; i <= r; i++) {
			brfore_i = i - 1;
			value_i = arr[i];
			while (brfore_i > p - 1 && arr[brfore_i] > value_i) {
				arr[brfore_i + 1] = arr[brfore_i--];
			}
			arr[brfore_i + 1] = value_i;
		}
	}
	
	public void swap(int[] arr, int x, int y) {
		int temp = arr[x];
		arr[x] = arr[y];
		arr[y] = temp;
	}
}
